package leetcode.code0664;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 错误的，不枚举中间是不行的
 *
 * @author CaoYu
 * @date 2022年1月9日
 * @description
 */
public class Solution2 implements IDebug {

	public int strangePrinter(String s) {
		int len = s.length();
		char[] cs = s.toCharArray();
		Integer[][] dp = new Integer[len][len];
		for (int i = len - 1; i >= 0; i--) {
			dp[i][i] = 1;
			for (int j = i + 1; j < len; j++) {
				this.f(cs, i, j, dp);
			}
		}
		HelpDebug.print(dp);
		return dp[0][len - 1];
	}

	private int f(char[] cs, int l, int r, Integer[][] dp) {
		if (l == r) {
			return 1;
		}
		if (dp[l][r] != null) {
			return dp[l][r];
		}
		int ans = Integer.MAX_VALUE;
		if (cs[l] == cs[r]) {
			if (l + 1 < cs.length && r - 1 >= 0 && r - 1 >= l + 1) {
				ans = this.f(cs, l + 1, r - 1, dp);
			}
			if (l + 1 < cs.length && l + 1 <= r) {
				ans = Math.min(ans, this.f(cs, l + 1, r, dp));
			}
			if (r - 1 >= 0 && r - 1 >= l) {
				ans = Math.min(ans, this.f(cs, l, r - 1, dp));
			}
		}
		if (l + 1 < cs.length && l + 1 <= r) {
			ans = Math.min(ans, this.f(cs, l + 1, r, dp) + 1);
		}
		if (r - 1 >= 0 && l <= r - 1) {
			ans = Math.min(ans, this.f(cs, l, r - 1, dp) + 1);
		}
		dp[l][r] = ans;
		return ans;

	}

	@Override
	public void debug1() {
		HelpDebug.compare(2, this.strangePrinter("aaabbb"));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(6, this.strangePrinter("sdfasdf"));

	}

	@Override
	public void debug3() {
		HelpDebug.compare(2, this.strangePrinter("aba"));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
//		D.debug14(so);

	}

}
